# coding=utf-8
from graph import *
import random


def random_set():
    """
    生成一个集合
    :return:set
    """
    s = set([])
    while len(s) < 10:
        s.add(random.randint(1, 100))
    return s


def can_add_edge(num1, num2):
    """
    判断两个数的个位或十位是否相等
    :param num1: 进行匹配的数
    :param num2: 进行被匹配的数
    :return: bool
    """
    if num1 == num2:
        return False
    if num1 < 10:
        if num2 < 10:
            return False
        else:
            if num1 == num2 % 10 or num1 == num2 / 10:
                return True
            else:
                return False
    else:
        if num2 < 10:
            if num1 % 10 == num2 or num1 / 10 == num2:
                return True
            else:
                return False
        else:
            if num1 % 10 == num2 % 10 or num1 % 10 == num2 / 10 or num1 / 10 == num2 % 10 or num1 / 10 == num2 / 10:
                return True
            else:
                return False


def build_graph(g, l):
    """
    构建一个图
    :param g: Graph
    :param l: list
    :return: Graph
    """
    for num1 in l:
        for num2 in l:
            if can_add_edge(num1, num2):
                g.add_edge(num1, num2)
    return g


if __name__ == '__main__':
    g = BFSGraph()
    vertex_list = list(random_set())
    g = build_graph(g, vertex_list)
    g.bfs(vertex_list[0])  # 设置一个起点
    print g.travers(vertex_list[-1])  # 设置终点输出路径
